package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

import java.util.Arrays;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/minimum-number-of-operations-to-make-array-continuous/">2009. 使数组连续的最少操作数</a>
 */
public class Solution2009 extends BaseSolution {

    public int minOperations(int[] nums) {
        Arrays.sort(nums);

        // 定位初始窗口
        sameC = 0;
        int left = 0, right = getNextRight(nums, 0, 1);

        int maxLen = right - left - sameC;

        // 滑动窗口
        while (right < nums.length) {
            // left 下一个不等的数字
            int lastLeft = nums[left++];
            while (left < nums.length) {
                if (nums[left] != lastLeft) {
                    break;
                }
                left++;
                sameC--;
            }

            // right 找到以新的left起始的最大右边界
            right = getNextRight(nums, left, right);
            maxLen = Math.max(maxLen, right - left - sameC);
        }

        return nums.length - maxLen;
    }

    int sameC = 0;

    private int getNextRight(int[] nums, int left, int right) {
        while (true) {
            if (right >= nums.length) {
                break;
            }
            if (nums[right] - nums[left] >= nums.length) {
                break;
            }
            if (nums[right] == nums[right - 1]) {
                sameC++;
            }
            right++;
        }
        return right;
    }

    public static void main(String[] args) {
        Solution2009 solution = new Solution2009();
        System.out.println(solution.minOperations(new int[] {
                1,10,100,1000
        }));
    }
}